package tree.fullTree;

import pojo.TreeNode;

/**
 * 功能描述: 完全二叉树工具类: 判断一颗树是否是完全二叉树
 *      nodes = 2^h - 1 满足这个条件一定是完全二叉树
 * 2024/06/09
 *
 * @author ZhangYi
 */
public class FullTreeUtils {
    /**
     * 功能描述:
     * 2024/06/09
     * <p>
     * ZhangYi
     */
    public static class Info{
        private int nodes;
        private int height;

        public Info(int nodes,
                    int height) {
            this.nodes = nodes;
            this.height = height;
        }
    }


    public boolean isFullTree(TreeNode treeNode){
        if (treeNode == null){
            return true;
        }

        return process(treeNode).nodes == (1 << process(treeNode).height) - 1;
    }

    private Info process(TreeNode treeNode) {
        if (treeNode == null){
            return new Info(0,0);
        }
        Info leftInfo = process(treeNode.left);
        Info rightInfo = process(treeNode.right);
        int height = Math.max(leftInfo.height,rightInfo.height)+1;
        int nodes = leftInfo.nodes+rightInfo.nodes+1;
        return new Info(nodes,height);
    }


    public static void main(String[] args) {
        TreeNode treeNode = generateNonBalanceSearchTree();
        System.out.println(new FullTreeUtils().isFullTree(treeNode));
        TreeNode treeNode1 = generateBalanceSearchTree();
        System.out.println(new FullTreeUtils().isFullTree(treeNode1));
    }

    /**
     * 生成平衡搜索树
     *
     * @return {@code TreeNode }
     * @author ZhangYi
     */
    private static TreeNode generateBalanceSearchTree() {
        TreeNode treeNode = new TreeNode(23,
                                         "1");
        treeNode.left = new TreeNode(12,
                                     "2");
        treeNode.right = new TreeNode(34,"3");
        treeNode.left.left = new TreeNode(11,
                                          "4");
        treeNode.left.right = new TreeNode(13,
                                           "5");

        treeNode.right.left = new TreeNode(11,
                                          "4");
        //treeNode.right.right = new TreeNode(13,
        //                                   "5");

        return treeNode;
    }


    private static TreeNode generateNonBalanceSearchTree() {
        TreeNode treeNode = new TreeNode(23,
                                         "1");
        treeNode.left = new TreeNode(12,
                                     "2");
        treeNode.left.left = new TreeNode(11,
                                          "4");
        treeNode.left.right = new TreeNode(13,
                                           "5");

        treeNode.left.left.left = new TreeNode(10,
                                               "9");
        treeNode.left.left.left.left = new TreeNode(9,
                                                    "10");
        treeNode.left.left.left.left.left = new TreeNode(8,
                                                         "11");

        treeNode.right = new TreeNode(34,
                                      "3");
        treeNode.right.left = new TreeNode(33,
                                           "6");
        treeNode.right.right = new TreeNode(35,
                                            "7");
        treeNode.right.right.right = new TreeNode(36,
                                                  "8");
        return treeNode;
    }
}
